package sivan.test;

/**
 * 堆排序。添加自下而上。删除自上而下
 */
public class HeapDemo {

    static int[] arrays = new int[20];
    static int index = 0;

    public static void main(String[] args) {
        int[] t = new int[]{6, 8, 3, 2, 4, 7, 5, 10, 1, 9};
        buildHeap(t);
        offer(11);
//
        remove(4);
        heapSort();
        System.out.println(arrays);
    }


    public static void heapSort() {
        int d = index;
        for (int i = 0; i < d; i++) {
            int temp = arrays[0];
            arrays[0] = arrays[index - 1];
            arrays[index - 1] = temp;
            index--;
            removeIndex(0, index);
        }
    }

    private static void offer(int val) {
        if (val >= arrays.length) {
            return;
        }

        arrays[index++] = val;
        shiftUp(index - 1);
    }

    public static void buildHeap(int[] arr) {
        for (int a : arr) {
            offer(a);
        }
    }

    public static int parent(int index) {
        return (index - 1) / 2;
    }

    public static int left(int index) {
        return 2 * index + 1;
    }

    private static int right(int index) {
        return 2 * index + 2;
    }

    public static void shiftUp(int i) {
        int p = parent(i);
        int val = arrays[i];
        if (arrays[p] > val) {
            arrays[i] = arrays[p];
            arrays[p] = val;
            shiftUp(p);
        }
    }

    public static void remove(int a) {
        int temp = arrays[a];
        System.arraycopy(arrays, a + 1, arrays, a, index - a);
        arrays[index - 1] = temp;
        index--;
        removeIndex(a, index);
    }

    private static void removeIndex(int i, int size) {
        int l = left(i);
        int r = right(i);
        int t = i;
        int s = arrays[i];
        if (l < size && arrays[l] < s) {
            t = l;
            s = arrays[l];
        }

        if (r < size && arrays[r] < s) {
            t = r;
        }

        if (t != i) {
            int temp = arrays[t];
            arrays[t] = arrays[i];
            arrays[i] = temp;
            removeIndex(t, size);
        }
    }
}
